{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums: [int], target: int) -> [int]:\n",
    "        get_indexes = lambda x, xs: [i for (y, i) in zip(xs, range(len(xs))) if x == y]\n",
    "        t_nums = nums[:]\n",
    "        t_nums.sort()\n",
    "        min_num = t_nums[0]\n",
    "        # right shift if min_num < 0\n",
    "        if min_num < 0:\n",
    "            # target should add double min_num\n",
    "            target = target - min_num*2\n",
    "            for i in range(len(t_nums)):\n",
    "                t_nums[i] = t_nums[i] - min_num\n",
    "                nums[i] = nums[i] - min_num\n",
    "        # locate left pointer and right pointer\n",
    "        left = 0\n",
    "        for i in range(len(t_nums)-1, 0, -1):\n",
    "            if t_nums[i] > target:\n",
    "                continue\n",
    "            else:\n",
    "                right = i\n",
    "                break\n",
    "        while left < right:\n",
    "            cur = t_nums[left] + t_nums[right]\n",
    "            if cur == target:\n",
    "                if t_nums[left] == t_nums[right]:\n",
    "                    return get_indexes(t_nums[left], nums)\n",
    "                else:    \n",
    "                    return [nums.index(t_nums[left]), nums.index(t_nums[right])]\n",
    "            elif cur > target:\n",
    "                right = right - 1\n",
    "            elif cur < target:\n",
    "                left = left + 1\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = Solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [-3,4,3,90]\n",
    "target = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2]"
      ]
     },
     "execution_count": 172,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s.twoSum(nums, target)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "py3",
   "language": "python",
   "name": "py3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
